package org.shj.dhsjjg.minpath;

/**
 * 迪杰斯特拉算法解决网络图中，由一个顶点到达另一个顶点的最短路径
 * 示例参见： minPath.png ，本例打印出V0到V8的最短路径
 * 此算法一次只能算出某个给定顶点至其余顶点的最短路径。 此例是设置 了 int begin = 0
 * 代表此例可得出V0顶点至其它顶点的最短路径
 * @author huangjian
 *
 */
public class Dijkstra {

	public static int M = Integer.MAX_VALUE / 2;
	public static void main(String[] args){
		int MaxVex = 9;  //顶点的个数
		int[] pathMatrix = new int[MaxVex]; //用于存储最短路径下标的数组, pathMatrix[i] = j 表示到
											// 达 i 顶点的最短路径的前驱顶点是 j
		int[] shortPath = new int[MaxVex];  //用于存储到各点最短路径的权值和
		
		int begin = 0;   //设置起始顶点的下标
		int v, w, k = 0, min;
		int[] finalArr = new int[MaxVex]; //finalArr[w] = 1 表示已求得顶点V0到Vw的最短路径
		int[][] graph = init(); 
		
		for(v = 0 ; v < graph.length; v++){
			finalArr[v] = 0;     //全部顶点初始化为未知最短路径状态
			shortPath[v] = graph[begin][v]; //将与V0点有连线的顶点加上权值
			pathMatrix[v] = 0;   //初始化路径数组P为0；
		}
		shortPath[begin] = 0;  //V0 至 V0路径为0
		finalArr[begin] = 1;   //V0至V0不需要求路径
		
		for(v = 1; v < graph.length ; v++){
			min = M;
			for(w = 0; w < graph.length; w++){ //寻找离V0最近的顶点
				if(finalArr[w] != 1 && shortPath[w] < min){
					k = w;
					min = shortPath[w];   //w 顶点离V0 更近
				}
			}
			finalArr[k] = 1;    //将目前找到的最近的顶点设为1
			
			for(w = 0; w < graph.length; w++){
				if(finalArr[w] != 1 && (min + graph[k][w] < shortPath[w])){//如果经过V顶点的路径比现在的这条路径的长度短
					shortPath[w] = min + graph[k][w];
					pathMatrix[w] = k;
				}
			}
		}
		
		//从pathMatrix中可以得到从顶点(V0)到任意顶点的最短的路径，例如： V0 --> V8, 可从 pathMatrix[8]的值(假设是7)得到到达V8的前驱最短路径顶点是7
		//再由pathMatrix[7]的值得到V7的前驱顶点，直至V0
		int i = 8; //V8顶点的下标
		while( i != 0){
			System.out.print("V" + i + "<--");
			i = pathMatrix[i];
		}
		System.out.print("V0");
	}
	
	//把图的信息初始化成一个二维数组，用极大值M代表两点之间无直接连线, M 并没有取Integer.MAX_VALUE以，是因为后面有进行  min + graph[k][w] 的操作，取最大值的话，加法会溢出
	private static int[][] init(){
		return new int[][]{
				{0, 1, 5, M, M, M, M, M, M},
				{1, 0, 3, 7, 5, M, M, M, M},
				{5, 3, 0, M, 1, 7, M, M, M},
				{M, 7, M, 0, 2, M, 3, M, M},
				{M, 5, 1, 2, 0, 3, 6, 9, M},
				{M, M, 7, M, 3, 0, M, 5, M},
				{M, M, M, 3, 6, M, 0, 2, 7},
				{M, M ,M, M, 9, 5, 2, 0, 4},
				{M, M, M, M, M, M, 7, 4, 0}
				
		};
	}
}
